package me.eg.ten;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 699. 掉落的方块
 * <p>
 * 在无限长的数轴（即 x 轴）上，我们根据给定的顺序放置对应的正方形方块。
 * <p>
 * 第 i 个掉落的方块（positions[i] = (left, side_length)）是正方形，其中 left 表示该方块最左边的点位置(positions[i][0])，side_length 表示该方块的边长(positions[i][1])。
 * <p>
 * 每个方块的底部边缘平行于数轴（即 x 轴），并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落，并保持静止后，才开始掉落新方块。
 * <p>
 * 方块的底边具有非常大的粘性，并将保持固定在它们所接触的任何长度表面上（无论是数轴还是其他方块）。邻接掉落的边不会过早地粘合在一起，因为只有底边才具有粘性。
 * <p>
 *  
 * <p>
 * 返回一个堆叠高度列表 ans 。每一个堆叠高度 ans[i] 表示在通过 positions[0], positions[1], ..., positions[i] 表示的方块掉落结束后，目前所有已经落稳的方块堆叠的最高高度。
 * <p>
 * 链接：https://leetcode-cn.com/problems/falling-squares
 */
public class FallingSquares {
    /**
     * 解法：线段树 + 离散化
     * 时间复杂度：O(N * logN)
     * 空间复杂度：O(N)
     * @param positions
     * @return
     */
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        // 1. 坐标离散化
        int[] pos = new int[n * 2];
        for (int i = 0; i < n; i++) {
            pos[i * 2] = positions[i][0];
            pos[i * 2 + 1] = positions[i][1] + positions[i][0] - 1;
        }
        // 1.1 坐标排序
        Arrays.sort(pos);
        // 1.2 坐标去重
        int m = 0;
        for (int i = 0; i < n * 2; i++) {
            if (i == 0 || pos[i] != pos[i - 1]) pos[m++] = pos[i];
        }

        List<Integer> ans = new ArrayList<>();
        // 2. 线段树
        SegmentTree segmentTree = new SegmentTree(new int[m]);
        for (int i = 0; i < n; i++) {
            int left = getHashIndex(pos, m, positions[i][0]);
            int right = getHashIndex(pos, m, positions[i][1] + positions[i][0] - 1);
            // 2.1 获取方块所在区间原最大值
            int currMax = segmentTree.query(left, right);
            // 2.1 更新方块所在区间最大值 = 方块所在区间原最大值 + 当前方块边长
            segmentTree.update(left, right, currMax + positions[i][1]);
            // 2.3 获取整个区间原最大值 -> 答案
            currMax = segmentTree.query(1, m);
            ans.add(currMax);
        }
        return ans;
    }

    private int getHashIndex(int[] pos, int m, int val) {
        int left = 0, right = m;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (pos[mid] == val) return mid;
            if (pos[mid] < val) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    /**
     * 线段树
     */
    class SegmentTree {
        private SegmentTreeNode[] tree;

        public SegmentTree(int[] nums) {
            tree = new SegmentTreeNode[nums.length * 4];
            build(nums, 1, 0, nums.length - 1);
        }

        public void update(int index, int val) {
            updateAt(1, index, val);
        }

        public void update(int left, int right, int val) {
            updateSection(1, left, right, val);
        }

        public int query(int left, int right) {
            return query(1, left, right);
        }

        /**
         * 构建线段树
         *
         * @param nums
         * @param pos
         * @param l
         * @param r
         */
        private void build(int[] nums, int pos, int l, int r) {
            SegmentTreeNode node = new SegmentTreeNode(l, r);
            tree[pos] = node;
            if (l == r) {
                node.max = nums[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(nums, pos * 2, l, mid);
            build(nums, pos * 2 + 1, mid + 1, r);
            node.max = Math.max(tree[pos * 2].max, tree[pos * 2 + 1].max);
        }

        /**
         * 单个节点更新
         *
         * @param pos
         * @param index
         * @param val
         */
        private void updateAt(int pos, int index, int val) {
            int l = tree[pos].l, r = tree[pos].r;
            if (l == r) {
                tree[pos].max = val;
                return;
            }
            spread(pos);
            int mid = (l + r) >> 1;
            if (index <= mid) update(pos * 2, index, val);
            else update(pos * 2 + 1, index, val);
            tree[pos].max = Math.max(tree[pos * 2].max, tree[pos * 2 + 1].max);
        }

        /**
         * 区间更新
         *
         * @param pos
         * @param left
         * @param right
         * @param delta
         */
        private void updateSection(int pos, int left, int right, int delta) {
            if (tree[pos].l >= left && tree[pos].r <= right) {
                tree[pos].max = delta;
                tree[pos].mark = delta;
                return;
            }
            spread(pos);
            int mid = (tree[pos].l + tree[pos].r) >> 1;
            if (left <= mid) updateSection(pos * 2, left, right, delta);
            if (right > mid) updateSection(pos * 2 + 1, left, right, delta);
            tree[pos].max = Math.max(tree[pos * 2].max, tree[pos * 2 + 1].max);
        }

        /**
         * 区间查询
         *
         * @param pos
         * @param left
         * @param right
         * @return
         */
        private int query(int pos, int left, int right) {
            if (tree[pos].l >= left && tree[pos].r <= right) {
                return tree[pos].max;
            }
            spread(pos);
            int ans = 0;
            int mid = (tree[pos].l + tree[pos].r) >> 1;
            if (left <= mid) ans = Math.max(ans, query(pos * 2, left, right));
            if (right > mid) ans = Math.max(ans, query(pos * 2 + 1, left, right));
            return ans;
        }

        private void spread(int pos) {
            if (tree[pos].mark != 0) { // 有懒惰标志
                int mark = tree[pos].mark;
                tree[pos * 2].max = mark;
                tree[pos * 2].mark = mark;
                tree[pos * 2 + 1].max = mark;
                tree[pos * 2 + 1].mark = mark;
                tree[pos].mark = 0;
            }
        }

        class SegmentTreeNode {
            public int l;
            public int r;
            public int max;
            public int mark;

            public SegmentTreeNode(int l, int r) {
                this.l = l;
                this.r = r;
            }
        }
    }
}

